#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

struct TreeNode {
  char ch;
  int freq;
  TreeNode* left;
  TreeNode* right;
  TreeNode(char _ch, int _freq) : ch(_ch), freq(_freq), left(nullptr), right(nullptr) {}
};

struct Compare {
  bool operator()(const TreeNode* lhs, const TreeNode* rhs) const {
    return lhs->freq > rhs->freq;
  }
};

void generateHuffmanTree(string str) {
  unordered_map<char, int> freqMap;
  for (char ch : str) {
    freqMap[ch]++;
  }

  priority_queue<TreeNode*, vector<TreeNode*>, Compare> pq;
  for (auto& entry : freqMap) {
    TreeNode* node = new TreeNode(entry.first, entry.second);
    pq.push(node);
  }

  while (pq.size() > 1) {
    TreeNode* left = pq.top();
    pq.pop();

    TreeNode* right = pq.top();
    pq.pop();

    TreeNode* combinedNode = new TreeNode('#', left->freq + right->freq);
    combinedNode->left = left;
    combinedNode->right = right;

    pq.push(combinedNode);
  }

  TreeNode* root = pq.top();

  unordered_map<char, string> huffmanCodeMap;
  string code = "";
  generateHuffmanCode(root, code, huffmanCodeMap);

  cout << "Huffman Codes:" << endl;
  for (auto& entry : huffmanCodeMap) {
    cout << entry.first << ": " << entry.second << endl;
  }
}

void generateHuffmanCode(TreeNode* root, string code, unordered_map<char, string>& huffmanCodeMap) {
  if (!root) {
    return;
  }

  if (!root->left && !root->right) {
    huffmanCodeMap[root->ch] = code;
  }

  generateHuffmanCode(root->left, code + "0", huffmanCodeMap);
  generateHuffmanCode(root->right, code + "1", huffmanCodeMap);
}

int main() {
  string str = "hello world";

  generateHuffmanTree(str);

  return 0;
}